When a fleet of vehicles is used to deliver goods or provide services, finding for every vehicle the optimal route has many practical benefits, including the reductions of in-transit time, fuel consumption, and vehicle emission. In order to determine such optimal routes, a routing algorithm has first to compute, for every pair of customers to serve, the time required to travel from one to another. For any practical application, a high number of shortest-path problems must then be solved. A successful solution to a shortest path problem relies on at least two basic foundations: one is the data used to represent the geographical information and the other one is the search algorithm.
The geographical information, such as an electronic map of a road network, is typically operated by a data provider either free of charge or with charge. Such geographical information uses nodes and weights to represent points of interest along a road network and distances. The points of interest can be landmarks, intersections, business location, and etc. Generally speaking, the number of nodes included in such database depends on the size of the area that the database covers. For a small town, the number of nodes may be a few hundreds. For a region, the number of nodes may be a few millions. For a continent, the number of nodes may be a few hundred millions.
After the geographical information is available. Dijkstra's algorithm is a classical algorithm for finding the shortest paths from an electronic map. The following webpage provides an example illustrating how this algorithm works in a practical manner: http://optlab-server.sce.carleton.ca/POAnimations2007/DijkstraAlgo.html. In general, the Dijkstra's algorithm separates the nodes on a network, sometimes called graph, into two groups: a “solved” group and an “unsolved” group. The algorithm implements an iteration process, during which each iteration moves one node in the network from the unsolved group to the solved group. At the beginning, the solved group only has the starting node. The unsolved group has the remaining nodes. Then, the Dijkstra's algorithm starts from the starting node and visits all nodes in the unsolved group that are adjacent to the nodes in the solved group to search for the shortest distance from the starting node. After the first iteration, the algorithm identifies this extra node as a “solved” node and adds it to the solved group. The second iteration will visit the rest of unsolved nodes that are adjacent to the nodes in the “solved” group and identify one extra node as another “solved” one. Such iteration continues until the destination node is included in the “solved” group.
Although Dijkstra's algorithm can find an exact solution for the shortest path problem, it has certain drawbacks for practical applications. For large graphs such as those representing regional or continental maps, Dijkstra's process can be computationally intensive because such algorithm has to be called repeatedly, on a large map graph, for every customer to be served. In the transportation application, the time taken to solve the shortest-path problem is an important factor in evaluating the performance of a routing system. A manager using automated software to compute many driver routes based on preset schedules would expect a search result from the server in a few minutes. A routing algorithm based on Dijkstra's algorithm without modification would not be able to satisfy such need.
Various methods have been used to accelerate the Dijkstra's algorithm. The article titled “Engineering Fast Route Planning Algorithm,” Peter Sanders et al., WEA 2007, LNCS 4525, pp. 23-35, 2007 provides a general introduction on different methods to accelerate the Dijkstra's algorithm. A drawback of commonly used accelerating methods is that they rely on additional information of a graph to prioritize the search algorithm. For example, in a vehicle routing application, some accelerating algorithms use speed profile, highway hierarchies, and traffic volume to speed up the search process. But, this type of accelerating techniques puts higher demands on comparing resources because the additional data needs to be buffered and processed during the runtime of the search algorithm. Furthermore, using Dijkstra of Dijkstra-based algorithms requires the raw map data to be available. This data is however often unavailable, due to commercial and technological reasons. An external service is used instead to compute the distances by executing suitable queries. Such external service will itself hold the raw map data, but will not make it available to the routing service.